6.7 KB · ⇊ 3 parts · ⤓ Micron 6.7 KB · ⤓ HTML 47.0 KB

top

Der Backward-Algorithmus (auch Rückwärts-Algorithmus, Rückwärts-Prozedur) berechnet mit Hilfe von Backward-Variablen die Wahrscheinlichkeit, in einem gegebenen Hidden-Markov-Modell (HMM) eine bestimmte Symbolsequenz zu beobachten. Der Algorithmus verwendet die Programmiermethode der dynamischen Programmierung.

• Markov-Modell

• Aufgabenstellung und Backward-Variablen

• Algorithmus

• Komplexität

• Weitere Anwendungen

• Siehe auch

• Literatur

• Weblinks

Gegeben sei ein HMM λ λ = ( S ; V ; A ; B ; π π ) {\displaystyle \lambda =(S;V;A;B;\pi )} , wobei

• S {\displaystyle S} die Menge der verborgenen Zustände,

• V {\displaystyle V} das Alphabet der beobachtbaren Symbole,

• A {\displaystyle A} die Übergangsmatrix,

• B {\displaystyle B} die Matrix der Emissionswahrscheinlichkeiten,

• π π {\displaystyle \pi } die Anfangswahrscheinlichkeitsverteilung für die möglichen Anfangszustände,

bezeichnet.

Gegeben sei ein Wort o = o 1 o 2 … … o T ∈ ∈ V ∗ ∗ {\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}} . Der Backward-Algorithmus berechnet nun P ( o | λ λ ) {\displaystyle P({\boldsymbol {o}}|\lambda )} , also die Wahrscheinlichkeit, im vorhandenen Modell λ λ {\displaystyle \lambda } tatsächlich die Beobachtung o {\displaystyle {\boldsymbol {o}}} zu machen.

Dafür werden die Backward-Variablen β β t ( i ) {\displaystyle \beta _{t}(i)} verwendet, sie bezeichnen die Wahrscheinlichkeit, das Suffix o t + 1 o t + 2 … … o T {\displaystyle o_{t+1}o_{t+2}\ldots o_{T}} zu beobachten, falls das HMM zum Zeitpunkt 1 ≤ ≤ t ≤ ≤ T {\displaystyle 1\leq t\leq T} im Zustand s i ∈ ∈ S {\displaystyle s_{i}\in S} gewesen ist:

β β t ( i ) = P ( o t + 1 o t + 2 … … o T | q t = s i ; λ λ ) {\displaystyle \beta _{t}(i)=P(o_{t+1}o_{t+2}\dotsc o_{T}|q_{t}=s_{i};\lambda )}

Die Backward-Variablen werden rekursiv bestimmt:

β β T ( i ) = 1 , 1 ≤ ≤ i ≤ ≤ | S | {\displaystyle \beta _{T}(i)=1,\qquad 1\leq i\leq \left|S\right|}

β β t ( i ) = ∑ ∑ j = 1 | S | b j ( o t + 1 ) ⋅ ⋅ a i j ⋅ ⋅ β β t + 1 ( j ) , 1 ≤ ≤ i ≤ ≤ | S | , 1 ≤ ≤ t < T {\displaystyle \beta _{t}(i)=\sum _{j=1}^{\left|S\right|}b_{j}(o_{t+1})\cdot a_{ij}\cdot \beta _{t+1}(j),\qquad 1\leq i\leq \left|S\right|,\ 1\leq t<T}

P ( o | λ λ ) = ∑ ∑ j = 1 | S | π π j ⋅ ⋅ b j ( o 1 ) ⋅ ⋅ β β 1 ( j ) {\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{\left|S\right|}\pi _{j}\cdot b_{j}(o_{1})\cdot \beta _{1}(j)}

Die Matrix aller Backward-Variablen braucht O ( | S | ⋅ ⋅ T ) {\displaystyle O(|S|\cdot T)} Speicher, werden die Zwischenergebnisse im Anschluss nicht mehr verwendet, so reduziert sich der Platzbedarf auf O ( | S | ) {\displaystyle O(|S|)} , da nur mehr zwei Spalten der Länge | S | {\displaystyle |S|} benötigt werden, um die Werte von β β t + 1 ( i ) {\displaystyle \beta _{t+1}(i)} und β β t ( i ) {\displaystyle \beta _{t}(i)} in jedem Rekursionsschritt zu speichern.

Für jede einzelne Variable wird über | S | {\displaystyle |S|} Zeilen summiert, also liegt die Laufzeit in O ( | S | 2 ⋅ ⋅ T ) {\displaystyle O(|S|^{2}\cdot T)} .

Die Backward-Variablen β β t ( i ) {\displaystyle \beta _{t}(i)} werden zusammen mit den Forward-Variablen α α t ( i ) = P ( o 1 , o 2 , … … , o t , q t = s i | λ λ ) {\displaystyle \alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=s_{i}|\lambda )} für den Baum-Welch-Algorithmus zur Lösung des mit Hidden-Markov-Modellen gegebenen Lernproblems benötigt.

Außerdem ermöglicht deren Kenntnis die Bestimmung der Wahrscheinlichkeit bei der Beobachtung von o {\displaystyle {\boldsymbol {o}}} zu einem festen Zeitpunkt t {\displaystyle t} im Zustand s i {\displaystyle s_{i}} gewesen zu sein, denn nach dem Satz von Bayes gilt:

P ( q t = s i | o ; λ λ ) = α α t ( i ) ⋅ ⋅ β β t ( i ) P ( o | λ λ ) {\displaystyle P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}}

• Forward-Algorithmus

• Viterbi-Algorithmus

• Baum-Welch-Algorithmus

• Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison: Biological sequence analysis. Probabilistic models of proteins and nucleic acids. 11th printing, corrected 10th reprinting. Cambridge University Press, Cambridge u. a. 2006, ISBN 0-521-62971-3, S. 59–60.

• Ernst G. Schukat-Talamazzini: Spezielle Musteranalysesysteme. (PDF, 1,3 MB). Vorlesung im Wintersemester 2012/2013 an der Universität Jena. Kapitel 5, Folie 34 ff.